package outoforder.leetcode01;

import java.util.HashMap;

/**
 * @author shhjiang_001
 * @create 2020-07-09 22:19
 */
public class Solution146 {
    private HashMap<Integer,Node> map;
    private DoubleList cache;
    private int cap;
    public Solution146(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if (!map.containsKey(key)){
            return -1;
        }
        int val = map.get(key).val;
        put(key,val);
        return val;
    }

    public void put(int key, int value) {
        Node x = new Node(key, value);
        if (map.containsKey(key)){
            cache.remove(map.get(key));
            cache.addFirst(x);
            map.put(key,x);
        }else {
            if (cap == cache.size()){
                Node last = cache.removeLast();
                map.remove(last.key);
            }
        }
        cache.addFirst(x);
        map.put(key,x);
    }
}
class Node{
    int key;
    int val;
    Node next;
    Node prev;
    Node(int k,int val){
        this.key = k;
        this.val = val;
    }
}
class DoubleList{
    void addFirst(Node x){

    }
    void remove(Node x){

    }
    Node removeLast(){
        return null;
    }
    int size(){
        return 0;
    }
}
